【题解】 [NOI2001]食物链 并查集 luoguP2024 | Qiuly's blog!

【题解】 [NOI2001]食物链 并查集 luoguP2024

Posted on | Edited on | In | Comments:

并不是很难。

首先，我们将一个点 $x$ 拆分成三个点：$x_{eat},x_{sim},x_{emy}$， $x_{eat}$ 表示 $x$ 的食物，$x_{sim}$ 表示 $x$ 的同类，$x_{emy}$ 表示 $x$ 的天敌。

然后，对于一句真话：

  • 如果是表示 $x​$ 是 $y​$ 的同类，那么很显然，$x​$ 的食物就是 $y​$ 的食物， $x​$ 的天敌就是 $y​$ 的天敌，于是讲 $x_{sim}​$ 和 $y_{sim}​$ 所在的并查集合并，将 $x_{eat}​$ 和 $y_{eat}​$ 所在的并查集合并，最后将 $x_{emy}​$ 和 $y_{emy}​$ 所在的并查集合并即可。
  • 如果这句表示 $x$ 吃 $y$ ，那么很显然，$x$ 的食物就是 $y$ 的同类，$x$ 的天敌就是 $y$ 的食物(因为是环形)，$x$ 的同类都是 $y$ 的天敌，故将这些关系的并查集一次合并即可。

怎么判断一句话的真假呢？

显然，如果 $x>n||y>n$ 就是假话，对于两个操作：

  • 如果表示 $x​$ 是 $y​$ 的同类，那么 $x_{eat}​$ 不能和 $y_{sim}​$ 在同一个并查集中，$x_{sim}​$ 不能和 $y_{eat}​$ 在同一个并查集中，否则就与前面的话冲突了。
  • 如果表示 $x$ 吃 $y$ ，首先 $x$ 和 $y$ 不能是同类(即 $x_{sim}$ 不能和 $y_{sim}$ 在一个并查集中)，然后 $y_{eat}$ 不能和 $x_{sim}$ 在一个并查集中，显然违反了以上的就是假话。

然后码量极小：

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>

const int N=5e4+2;
const int inf=1e9+9;
const int K=1e5+2;

int fa[N*3],ans,n,k;

inline int sim(int x){return x;};
inline int eat(int x){return x+n;};
inline int emy(int x){return x+n+n;};

int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);};

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n*3;++i)fa[i]=i;
    for(int i=1;i<=k;++i){
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(x>n||y>n){++ans;continue;}
        if(op==1){
            if(find(eat(x))==find(sim(y))||find(sim(x))==find(eat(y))){++ans;}
            else{
                fa[find(sim(x))]=find(sim(y));
                fa[find(eat(x))]=find(eat(y));
                fa[find(emy(x))]=find(emy(y));	
            }
        }else{
            if(find(sim(x))==find(sim(y))||find(sim(x))==find(eat(y))){++ans;}
            else{
                fa[find(eat(x))]=find(sim(y));
                fa[find(emy(x))]=find(eat(y));
                fa[find(sim(x))]=find(emy(y));
            }
        }	
    }
    printf("%d\n",ans);
    return 0;
}

我绝对不会告诉你们，我有一处地方 $sim$ 写成了 $sin$ 而调了半个小时

本文标题:【题解】 [NOI2001]食物链 并查集 luoguP2024

文章作者:Qiuly

发布时间:2019年02月22日 - 00:00

最后更新:2019年03月29日 - 13:53

原始链接:http://qiulyblog.github.io/2019/02/22/[题解]luoguP2024/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。